0279. 完全平方数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

给你一个整数 n，返回 和为 n 的完全平方数的最少数量。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

---

提示：

• 1 <= n <= 10^4

2. 🎯 s.1 - 动态规划

c

int numSquares(int n) {
    int* dp = (int*)malloc(sizeof(int) * (n + 1));
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = i; // 最坏情况全用 1
        for (int j = 1; j * j <= i; j++) {
            if (dp[i - j * j] + 1 < dp[i]) dp[i] = dp[i - j * j] + 1;
        }
    }
    int res = dp[n];
    free(dp);
    return res;
}

js

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
  const dp = new Array(n + 1).fill(Infinity)
  dp[0] = 0
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j * j <= i; j++) {
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1)
    }
  }
  return dp[n]
}

py

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0] + [float('inf')] * n
        for i in range(1, n + 1):
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
        return dp[n]

• 时间复杂度：$O(n\sqrt{n})$
• 空间复杂度：$O(n)$，dp 数组

算法思路：

• $dp[i]$ 表示和为 $i$ 的最少完全平方数个数
• 转移方程：$dp[i]=min(dp[i-j^2]+1)$，枚举所有 $j^2\le i$ 的完全平方数